package 链表;


/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/insertion-sort-list/
 */
public class _147_对链表进行插入排序 {
    /**
     * 利用两个指针 一个指向移动中的节点（lastSorted）  一个指向下一个要比较的节点(curr)
     * 当lastSorted比curr大时，则需要将小的排序到链表中
     * prev是指从头节点开始，到比curr大的前一个节点，将prev.next指向到curr
     * 即将curr排序
     * @param head 目标链表
     * @return ListNode
     */
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode lastSorted = head, curr = head.next;

        while (curr != null) {
            if (lastSorted.val <= curr.val) {
                lastSorted = curr;
                curr = curr.next;
            } else {
                ListNode prev = dummyHead;
                // 找到lastSorted的前一个节点
                while (prev.next.val < curr.val) {
                    prev = prev.next;
                }
                // 排序
                lastSorted.next = curr.next;
                curr.next = prev.next;
                prev.next = curr;
                curr = lastSorted.next;
            }
        }
        return dummyHead.next;
    }
}
